This application relates to database queries and, more particularly, to database queries that are encrypted to prevent the owner of a queried database from knowing the substance of the queries presented to the database.
It is often necessary for two or more or more parties that do not fully trust each other to selectively share data. For example, intelligence agency A may wish to let intelligence agency B to query a database of intelligence agency A, but only to the extent of only disclosing clearly relevant documents to intelligence agency B. Conversely, intelligence agency B is willing to search the database of intelligence agency A, but only if such a search does not reveal precisely what the subject of the search is.
Conventional search techniques do not permit this. Although a publication by Eu-Jin Goh, “Secure indexes for efficient searching on encrypted compressed data,” Cryptology ePrint Archive, Report 2003/216, 2003, http://eprint.iacr.org/2003/216/, describes an arrangement that employs Bloom filters, with encryption used for the hash functions, the described arrangement requires that all parties share all keys, which does not meet the goal of keeping the nature of the database search secret.